#使用k-means算法实现对新闻的聚类
import os
import math
import random

typeNameList = ["yule","business","it","sports","auto"]
sourceDir = "F:\\allfiles"

doc = []         #各文档词汇出现频次
docType = []     #文档类别划分
center = []      #类中心点

typeNum = []     #每个分类文章数
docTypeReal = [] #实际的类别划分

def ComputeDis(doc1, doc2):
        sum = 0.0
        for (wid, freq) in doc1.items():
                if wid in doc2:
                        d = freq - doc2[wid]
                        sum += d*d
                else:
                        sum += freq * freq
        for (wid, freq) in doc2.items():
                if wid not in doc1:
                        sum += freq * freq
        #sum = math.sqrt(sum)
        return sum

def distanceBetween(point1,point2):
    v = 0
    s = 0
    for k in (set(point1.keys()) ^ set(point2.keys())):
        v = point1.get(k,point2.get(k))
        s += v * v
        
    for k in (set(point1.keys()) & set(point2.keys())):
        v = point1.get(k) - point2.get(k)
        s += v * v

    return math.sqrt(s + 0.0)


#初始化操作
fileIndex = 0
typeIndex = 0

#加载文件
for fileName in os.listdir(sourceDir):

    fileIndex += 1

    #读取文章类别
    for i in range(len(typeNameList)):
        if fileName.find(typeNameList[i]) > 0:
            typeIndex = i
            break

    docTypeReal.append(i)

    page = open(sourceDir + "\\" + fileName,"r",encoding="UTF-8")

    pageWord = {}

    #读取单词出现次数
    for lines in page.readlines():
        for word in lines.replace('\n', ' ').split(' '):
            word = word.strip()
            if len(word) < 1: continue

            if word in pageWord:
                pageWord[word] += 1
            else:
                pageWord[word] = 1

    doc.append(pageWord.copy())
    
docType = [0]*len(doc)

#随机从doc选取k个点作为中点
for i in range(len(typeNameList)):
##    abc = random.randint(0,len(doc)-1)
##    print ("len(center):" + str(len(center)))
##    print ("len(doc):" + str(len(doc)))
##    print ("abc:" + str(abc))
    
    rIndex = random.randint(0,len(doc)-1)
    print("rIndex:" + str(rIndex))
    center.append(doc[rIndex].copy())
    
for i in range((len(center))):
    print("center:" + str(len(center[i])))


#循环10次k-means模型，看看效果
for times in range(2):
    
    #根据每个聚类中心，对所有文章进行分类
    for i in range(len(doc)):

        #记录最小距离和分类
        minDistance = 0
        minType = 0

        print("======" + str(i))
#        print("center:" + str(center))
#        print("len(center):" + str(len(center)))
        
        for j in range(len(center)):
#            distance = len(set(doc[i].keys()) ^ set(center.keys()))
            distance = ComputeDis(doc[i], center[j])

#            print("distance["+str(i)+"]["+str(j)+"]:" + str(distance))
            
            if j == 0 or minDistance > distance:
                minDistance = distance
                minType = j
                
#        print("minDistance:" + str(minDistance))
#        print("minType:" + str(minType))

        docType[i] = minType

    #重新计算每个分类中心
#    center = [{}]*len(typeNameList)
    center = [{},{"a":1},{"b":1},{"c":1},{"d":1}]
    typeNum = [0]*len(center)
    for i in range(len(doc)):
        typeNum[docType[i]] += 1
        for k,v in doc[i].items():
            if k in center:
                center[docType[i]][k] += v
            else:
                center[docType[i]][k] = v

    for i in range(len(typeNum)):
        print ("typeNum["+str(i)+"]:" + str(typeNum[i]))
            
    for i in range(len(docType)):
        print ("docType["+str(i)+"]:" + str(docType[i]))

    #中心点等于各分类点合计值除以点数
    for i in range(len(docType)):
        for k,v in center[docType[i]].items():
            center[docType[i]][k] = (center[docType[i]][k] + 0.0) / typeNum[docType[i]]
#        center[docType[i]] = (center[docType[i]][j] + 0.0) / typeNum[docType[i]]

##        for j in range(len(center[docType[i]])):
##            if typeNum[docType[i]] == 0 : continue
##            center[docType[i]][j] = (center[docType[i]][j] + 0.0) / typeNum[docType[i]]

    for i in range((len(center))):
        print("center:" + str(len(center[i])))

#    print("center:" + str(len(center)))
    
    #计算WCSS
    wcss = 0
    for i in range(len(doc)):
        wcss += ComputeDis(doc[i], center[docType[i]])

    print("wcss:" + str(wcss))















    
